package main

import (
	"fmt"
)

//todo 未解决,有点略难
func main() {
	arr := [][]byte{
		{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
		{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
		{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
		{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
		{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
		{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
		{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
		{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
		{'.', '.', '.', '.', '8', '.', '.', '7', '9'},
	}
	solveSudoku(arr)
}

type pointVal struct {
	X   int
	Y   int
	Val byte
}
type point struct {
	X int
	Y int
}

func contains(arr []byte, target byte) bool {
	if arr == nil {
		return false
	}
	for _, v := range arr {
		if v == target {
			return true
		}
	}
	return false
}

func solveSudoku(board [][]byte) {
	var arr []pointVal
	ignoremap := make(map[point][]byte)

	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board); j++ {
			if board[i][j] == '.' {
				val, _ := ignoremap[point{i, j}]
				for k := '1'; k <= '9' && !contains(val, byte(k)); k++ {
					board[i][j] = byte(k)
					if isValidSudoku(board) {
						arr = append(arr, pointVal{i, j, byte(k)})
						break
					}
				}
			}

			//循环完后还是没有值回溯

			if !isValidSudoku(board) {
				if len(arr) > 0 {

					key := point{i, j}
					val, ok := ignoremap[key]
					if ok {
						val = append(val, board[i][j])
					} else {
						ignoremap[key] = []byte{board[i][j]}
					}
					board[i][j] = '.'

					last := arr[len(arr)-1]
					i = last.X
					j = last.Y
					board[i][j] = last.Val
					arr = arr[:len(arr)-1] //remove last
				}
			}
		}
	}
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board); j++ {
			fmt.Printf("%v ", string(board[i][j]))
		}
		fmt.Println()
	}
	fmt.Println(arr)
}

func isValidSudoku(board [][]byte) bool {

	result := true
	var columns []byte
	var grids1 []byte
	var grids2 []byte
	var grids3 []byte
	for i := 0; i < 9; i++ {
		if i/3 == 1 {
			if len(grids1) == 9 {
				result = result && isValid(grids1) && isValid(grids2) && isValid(grids3)
				//fmt.Println(grids1)
				//fmt.Println(grids2)
				//fmt.Println(grids3)
				grids1 = []byte{}
				grids2 = []byte{}
				grids3 = []byte{}
			}
		} else if i/3 == 2 {
			if len(grids1) == 9 {
				result = result && isValid(grids1) && isValid(grids2) && isValid(grids3)
				//fmt.Println(grids1)
				//fmt.Println(grids2)
				//fmt.Println(grids3)
				grids1 = []byte{}
				grids2 = []byte{}
				grids3 = []byte{}
			}
		}
		for j := 0; j < 9; j++ {
			if j/3 == 0 { // 遇到3，遇到6
				grids1 = append(grids1, board[i][j])
			} else if j/3 == 1 {
				grids2 = append(grids2, board[i][j])
			} else if j/3 == 2 {
				grids3 = append(grids3, board[i][j])
			}
		}
	}
	result = result && isValid(grids1) && isValid(grids2) && isValid(grids3)

	//fmt.Println(grids1)
	//fmt.Println(grids2)
	//fmt.Println(grids3)

	for i := 0; i < len(board); i++ {
		columns = []byte{}
		result = result && isValid(board[i]) // 行检查

		for j := 0; j < len(board); j++ {
			columns = append(columns, board[j][i])
		}
		result = result && isValid(columns) // 列检查
	}
	return result
}

func isValid(arr []byte) bool {
	m := make(map[byte]byte, len(arr))
	for _, v := range arr {
		if v != byte('.') {
			if v < '1' || v > '9' {
				return false
			}
			_, ok := m[v]
			if ok {
				return false
			}
			m[v] = v
		}
	}
	return true
}
